package com.gjx.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
//103. 二叉树的锯齿形层次遍历
//
//给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
//
//例如：
//给定二叉树 [3,9,20,null,null,15,7],
//
//    3
//   / \
//  9  20
//    /  \
//   15   7
//返回锯齿形层次遍历如下：
//
//[
//  [3],
//  [20,9],
//  [15,7]
//]
import java.util.Queue;

public class Solution103 {
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
        	return res;
        }
        
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        boolean leftToRight = true;
        
        while (!q.isEmpty()) {
        	
        	int size = q.size();
        	
        	List<Integer> list = new LinkedList<>();
        		
        	for (int i=0; i<size; i++) {
        		TreeNode tn = q.poll();
        		
        		if (leftToRight) {
        			list.add(tn.val);
        		} else {
        			list.add(0, tn.val);
        		}

        		
    			if (tn.left != null) q.offer(tn.left);
    			if (tn.right != null) q.offer(tn.right);
        		
        	}
        	
        	res.add(list);
        	leftToRight = !leftToRight;
        	
        }
        return res;
    }
}
